//
// Created by PC on 2017/12/22.
//

#ifndef DFSANDCOMPONENTS_COMPONENTS_H
#define DFSANDCOMPONENTS_COMPONENTS_H
#include <iostream>
#include <cassert>
using namespace std;

template <typename Graph>
class Component{
private:
    Graph &G;
    bool *visited;
    int ccount;
    int *id;

    void dfs(int v) {
        visited[v]=true;
        id[v]=ccount;
        typename Graph::adjIterator adj(G,v);
        for(int w=adj.begin();!adj.end();w=adj.next())
            if (!visited[w])
                dfs(w);
    }
public:

    Component(Graph &graph) : G(graph) {

        visited=new bool[G.V()];
        id=new int[G.V()];
        for (int i = 0; i < G.V(); i++) {
            visited[i]= false;
            id[i]=-1;
        }
        for (int i = 0; i < G.V(); i++)
            if (!visited[i]) {
                dfs(i);
                ccount++;
            }
    }

    ~Component(){
        delete[] visited;
        delete[] id;
    }
    int count(){
        return ccount;
    }

    bool isConnected(int v, int w) {
        assert( v >= 0 && v < G.V() );
        assert( w >= 0 && w < G.V() );
        return id[v]==id[w];
    }
};

#endif //DFSANDCOMPONENTS_COMPONENTS_H
